// 解题思路：
// 第一步：先逆序链表 - 头插法，先定义指针 next 指向 cur 后面的节点，再 cur.next = head.next, head.next = cur, cur = next
// 第二步：再求和
// 第三步处理进位, 再把结果头插到 head 的后面

public class LinkedListAddition {
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        ListNode head = new ListNode(0);
        ListNode cur1 = reverse(head1);
        ListNode cur2 = reverse(head2);

        int carry = 0;

        while(cur1 != null || cur2 != null || carry != 0){
            if(cur1 != null) {
                carry += cur1.val;
                cur1 = cur1.next;
            }
            if(cur2 != null) {
                carry += cur2.val;
                cur2 = cur2.next;
            }
            ListNode cur = new ListNode(carry % 10);
            carry /= 10;
            cur.next = head.next;
            head.next = cur;
        }
        return head.next;
    }

    public ListNode reverse(ListNode head){
        ListNode newHead = new ListNode(0);
        ListNode cur = head;

        while(cur != null){
            ListNode next = cur.next;
            cur.next = newHead.next;
            newHead.next = cur;
            cur = next;
        }
        return newHead.next;
    }
}

class ListNode {
    int val;
    ListNode next = null;
    public ListNode(int val) {
        this.val = val;
    }
}
